package com.leetcode;

/**
 * 494. 目标和
 *
 * @author fy
 * @date 2022/3/31 11:53
 */
public class Solution494_1 {

    private int[][] dp;
    private int totalSum;

    public int findTargetSumWays(int[] nums, int target) {
        totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        dp = new int[nums.length][totalSum * 2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < totalSum; j++) {
                dp[i][j] = -1;
            }
        }
        return calcSum(nums, target, 0, 0);
    }

    private int calcSum(int[] nums, int target, int index, int sum) {
        if (dp[index][sum + totalSum] != -1) {
            return dp[index][sum];
        }
        if (index == nums.length) {
            if (target == sum) {
                return 1;
            } else {
                return 0;
            }
        }
        int res = 0;
        res += calcSum(nums, target, index + 1, sum + nums[index]);
        res += calcSum(nums, target, index + 1, sum - nums[index]);

        dp[index][sum + totalSum] = res;

        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 1, 1};
        int target = 3;

        int n = new Solution494().findTargetSumWays(nums, target);
        System.out.println(n);
    }
}
